package test;

import java.util.Arrays;

/**
 * 描述：
 *
 * @author hl
 * @version 1.0
 * @date 2020/10/30 21:09
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {2, 6, 8, 4, 4, 1, 3, 9, 6, 8};
        new MergeSort().mergesort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public void mergesort(int[] arr){
        if (arr == null || arr.length < 2) {
            return ;
        }
        mergesort(arr, 0, arr.length - 1);
    }

    private void mergesort(int[] arr, int l, int r) {
        if (l >= r) {
            return ;
        }
        int mid = l + ((r - l) >> 1);
        mergesort(arr, l, mid);
        mergesort(arr, mid + 1, r);
        merge(arr, l, r, mid);
    }

    private void merge(int[] arr, int l, int r, int mid) {
        int[] helper = new int[r - l + 1];
        int p1 = l;
        int p2 = mid + 1;
        int index = 0;
        while (p1 <= mid && p2 <= r){
            helper[index++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while(p1 <= mid){
            helper[index++] = arr[p1++];
        }
        while(p2 <= r){
            helper[index++] = arr[p2++];
        }
        for (int i = 0; i < helper.length; i++) {
            arr[l + i] = helper[i];
        }
    }
}
